package com.leo.leetcode.s100;

/**
 *
 * @author xuexiaolei
 * @version 2017年12月01日
 */
public class T69Sqrtx {
    public static int mySqrt(int x) {
        if (x < 2) return x;
        int low = 0;
        int high = x;
        while (high > low+1){
            int mid = (low+high)/2;
            long mid2 = (long) mid * mid;
            if (mid2 > x){
                high = mid;
            }else if (mid2 < x){
                low = mid;
            }else {
                return mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(0));
        System.out.println(mySqrt(1));
        System.out.println(mySqrt(4));
        System.out.println(mySqrt(5));
        System.out.println(mySqrt(8));
        System.out.println(mySqrt(9));
        System.out.println(mySqrt(10));
        System.out.println(mySqrt(12531251));
        System.out.println(Math.sqrt(12531251));
    }
}
